{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Choose Numbers From Two Arrays in Range"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: countSubranges"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #在两个数组的区间中选取数字"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你两个 <strong>下标从 0 开始</strong>，长度为 <code>n</code> 的整数数组 <code>nums1</code> 和 <code>nums2</code>。</p>\n",
    "\n",
    "<p>如果一个区间 <code>[l, r]</code> （<strong>包含左右端点</strong>，<code>0 &lt;= l &lt;= r &lt; n</code>）满足下列条件，那么这个区间就是 <strong>平衡</strong> 的：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>对每个在区间 <code>[l, r]</code> 范围内的 <code>i</code>，你需要选取&nbsp;<code>nums1[i]</code> 或者&nbsp;<code>nums2[i]</code>；</li>\n",
    "\t<li>从 <code>nums1</code> 中选取的数字和与从 <code>nums2</code> 中选取的数字和相等。（如果你没有从某个数组中选取任何数字，那么数字和被视为 <code>0</code>）。</li>\n",
    "</ul>\n",
    "\n",
    "<p>如果两个 <strong>平衡</strong> 的区间 <code>[l<sub>1</sub>, r<sub>1</sub>]</code> 和 <code>[l<sub>2</sub>, r<sub>2</sub>]</code> 满足下列条件之一，那么它们就是 <strong>不同</strong> 的：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>l<sub>1</sub> != l<sub>2</sub></code></li>\n",
    "\t<li><code>r<sub>1</sub> != r<sub>2</sub></code></li>\n",
    "\t<li>两个区间中的数字选取情况不同（也就是说，存在至少一个 <code>i</code>，使得在第一个区间中，<code>nums1[i]</code> 被选中, 而在第二个区间中，<code>nums2[i]</code> 被选中，或者相反的情况）。</li>\n",
    "</ul>\n",
    "\n",
    "<p>请返回 <strong>不同</strong> 的平衡的区间数目。由于答案可能很大，请返回答案 <strong>模 </strong><code>10<sup>9</sup>+7</code> 的结果。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> nums1 = [1,2,5], nums2 = [2,6,3]\n",
    "<strong>输出:</strong> 3\n",
    "<strong>解释:</strong> 平衡的区间有:\n",
    "- [0, 1], 我们选取 nums2[0] 和 nums2[1]。\n",
    "  从 <code>nums1</code> 中选取的数字和与从 <code>nums2</code> 中选取的数字和相等: 2 = 2.\n",
    "- [0, 2], 我们选取 nums1[0], nums2[1] 和 nums1[2]。\n",
    "  从 <code>nums1</code> 中选取的数字和与从 <code>nums2</code> 中选取的数字和相等: 1 + 5 = 6。\n",
    "- [0, 2], 我们选取 nums1[0], nums1[1] 和 nums2[2]。\n",
    "  从 <code>nums1</code> 中选取的数字和与从 <code>nums2</code> 中选取的数字和相等: 1 + 2 = 3。\n",
    "注意第二个区间和第三个区间是不同的。\n",
    "因为在第二个平衡的区间中，我们选取了 nums2[1]，但是在第三个平衡的区间中，我们选取了 nums1[1]。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> nums1 = [0,1], nums2 = [1,0]\n",
    "<strong>输出:</strong> 4\n",
    "<strong>解释:</strong> 平衡的区间有:\n",
    "- [0, 0], 我们选取 nums1[0]。\n",
    "  从 <code>nums1</code> 中选取的数字和与从 <code>nums2</code> 中选取的数字和相等: 0 = 0。\n",
    "- [1, 1], 我们选取 nums2[1]。\n",
    "  从 <code>nums1</code> 中选取的数字和与从 <code>nums2</code> 中选取的数字和相等: 0 = 0。\n",
    "- [0, 1], 我们选取 nums1[0] 和 nums2[1]。\n",
    "  从 <code>nums1</code> 中选取的数字和与从 <code>nums2</code> 中选取的数字和相等: 0 = 0。\n",
    "- [0, 1], 我们选取 nums2[0] 和 nums1[1]。\n",
    "  从 <code>nums1</code> 中选取的数字和与从 <code>nums2</code> 中选取的数字和相等: 1 = 1。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == nums1.length == nums2.length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 100</code></li>\n",
    "\t<li><code>0 &lt;= nums1[i], nums2[i] &lt;= 100</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [choose-numbers-from-two-arrays-in-range](https://leetcode.cn/problems/choose-numbers-from-two-arrays-in-range/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [choose-numbers-from-two-arrays-in-range](https://leetcode.cn/problems/choose-numbers-from-two-arrays-in-range/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,5]\\n[2,6,3]', '[0,1]\\n[1,0]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubranges(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        mod = 10**9+7\n",
    "        res = 0\n",
    "        ct = defaultdict(int)\n",
    "        for a,b in zip(nums1,nums2):\n",
    "            ct[0] += 1\n",
    "            ct2 = defaultdict(int)\n",
    "            for x in ct:\n",
    "                ct2[x+a] += ct[x]\n",
    "                ct2[x+a] %= mod\n",
    "                ct2[x-b] += ct[x]\n",
    "                ct2[x-b] %= mod\n",
    "            ct = ct2\n",
    "            res += ct[0]\n",
    "            res %= mod\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubranges(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        mod = 10**9+7\n",
    "        res = 0\n",
    "        ct = defaultdict(int)\n",
    "        for a,b in zip(nums1,nums2):\n",
    "            ct[0] += 1\n",
    "            ct2 = defaultdict(int)\n",
    "            for x in ct:\n",
    "                ct2[x+a] += ct[x]\n",
    "                ct2[x-b] += ct[x]\n",
    "            ct = ct2\n",
    "            res += ct[0]\n",
    "            res %= mod\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubranges(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        mod = 10**9+7\n",
    "        res = 0\n",
    "        ct = defaultdict(int)\n",
    "        for a,b in zip(nums1,nums2):\n",
    "            _ct = defaultdict(int)\n",
    "            _ct[a] += 1\n",
    "            _ct[-b] += 1\n",
    "            for x in ct:\n",
    "                _ct[x+a] += ct[x]\n",
    "                _ct[x-b] += ct[x]\n",
    "            ct = _ct\n",
    "            res += ct[0]\n",
    "            res %= mod\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubranges(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        mod = 10**9+7\n",
    "        res = 0\n",
    "        ct = defaultdict(int)\n",
    "        for a,b in zip(nums1,nums2):\n",
    "            ct[0] += 1\n",
    "            ct2 = defaultdict(int)\n",
    "            for x in ct:\n",
    "                ct2[x+a] += ct[x]\n",
    "                ct2[x-b] += ct[x]\n",
    "            ct = ct2\n",
    "            res += ct[0]\n",
    "        return res%mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubranges(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "      n = len(nums1)\n",
    "      s1, s2 = sum(nums1), sum(nums2)\n",
    "      f = [[0] * (s1 + s2 + 1) for _ in range(n)]\n",
    "      ans = 0\n",
    "      mod = 10**9 + 7\n",
    "      for i, (a, b) in enumerate(zip(nums1, nums2)):\n",
    "        f[i][a + s2] += 1\n",
    "        f[i][-b + s2] += 1\n",
    "        if i:\n",
    "          for j in range(s1 + s2 + 1):\n",
    "            if j >= a:\n",
    "              f[i][j] = (f[i][j] + f[i - 1][j - a]) % mod\n",
    "            if j + b < s1 + s2 + 1:\n",
    "              f[i][j] = (f[i][j] + f[i - 1][j + b]) % mod\n",
    "        ans = (ans + f[i][s2]) % mod\n",
    "      return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubranges(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "\n",
    "        n = len(nums1)\n",
    "        dp = [collections.defaultdict(int) for _ in range(n)]\n",
    "     \n",
    "        MODX = 10**9+7\n",
    "\n",
    "\n",
    "\n",
    "        dp[0][nums1[0]] += 1\n",
    "        dp[0][-nums2[0]] += 1\n",
    "\n",
    "        ans = dp[0][0]\n",
    "        for i in range(1,n):\n",
    "            dp[i][nums1[i]] += 1\n",
    "            dp[i][-nums2[i]] += 1\n",
    "            for pre_sum in dp[i-1]:\n",
    "                dp[i][pre_sum+nums1[i]] += dp[i-1][pre_sum]\n",
    "                dp[i][pre_sum-nums2[i]] += dp[i-1][pre_sum]\n",
    "\n",
    "                dp[i][pre_sum+nums1[i]]%= MODX\n",
    "                dp[i][pre_sum-nums2[i]]  %= MODX\n",
    "            \n",
    "            ans += dp[i][0]\n",
    "            ans %= MODX\n",
    "\n",
    "        return ans\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
